Error Correction Codes (ECCs) are commonly used in communication and storage systems. Various physical phenomena occurring both in communication channels and in storage devices result in noise effects that corrupt the communicated or stored information. Error correction coding schemes can be used for protecting the communicated or stored information against the resulting errors. This is done by encoding the information before transmission through the communication channel or storage in the memory device. The encoding process transforms an information bit sequence i into a codeword v by adding redundancy to the information. This redundancy can then be used in order to recover the information from a corrupted codeword y through a decoding process. An ECC decoder decodes the corrupted codeword y and recovers a bit sequence that should be equal to the original information bit sequence i with high probability.
Iterative coding schemes have become very popular in recent years, due to their ability to achieve near Shannon limit performance at low decoding complexity. One family of iterative decoders operates on a code that may be defined using a bipartite graph describing the interconnections between data bits at bit nodes of the graph, and parity check equations at check nodes of the graph. In this case, decoding can be viewed as an iterative message passing over edges of the graph connecting the bit nodes and check nodes.
One popular class of iterative codes is Low-Density Parity-Check (LDPC) codes. An LDPC code is a linear binary block code defined by a sparse parity-check matrix H. As shown in FIG. 1, the code can also be defined by a sparse bipartite graph G=(V, C, E) with a set V of N bit nodes (N=13 in FIG. 1), a set C of M check nodes (M=10 in FIG. 1) and a set E (E=38 in FIG. 1) of edges connecting bit nodes to check nodes. The bit nodes correspond to the codeword bits and the check nodes correspond to parity-check constraints on the bits. A bit node is connected by edges to the check nodes in which it participates.
LDPC codes can be decoded using iterative message passing decoding algorithms. These algorithms operate by exchanging messages between bit nodes and check nodes over the edges of the underlying bipartite graph representing the code. The decoder is provided with initial estimates of the codeword bits (based on the communication channel output or based on the read memory content). These initial estimates are refined and improved by imposing the parity-check constraints that the bits should satisfy as a valid codeword. This is done by exchanging information between the bit nodes representing the codeword bits and the check nodes representing parity-check constraints on the codeword bits, using the messages that are passed along the graph edges.
Decoding algorithms may be divided into two categories, namely soft decision decoding and hard-decision decoding.
Soft decision decoding is known to achieve results very close to the Shannon limit of the channel. However, this comes with a price in the form of computational complexity.
In soft decision decoding algorithms, it is common to utilize “soft” bit estimations, which convey both the bit estimation and the reliability of the estimation.
The bit estimations conveyed by the messages passed along the graph edges can be expressed in various forms. A common measure for expressing “soft” bit estimation is Log-Likelihood Ratio (LLRs), which is defined in the following equation:
                    LLR        =                  log          ⁢                                          ⁢                                    Pr              ⁡                              (                                  v                  =                                      0                    |                                          current                      ⁢                                                                                          ⁢                      constraints                      ⁢                                                                                          ⁢                      and                      ⁢                                                                                          ⁢                      observations                                                                      )                                                    Pr              ⁡                              (                                  v                  =                                      1                    |                                          current                      ⁢                                                                                          ⁢                      constraints                      ⁢                                                                                          ⁢                      and                      ⁢                                                                                          ⁢                      observations                                                                      )                                                                        (        1        )            where the “current constraints and observations” are the various parity-check constraints taken into account in computing the message at hand, and the observations v correspond to the bits participating in these parity checks. Without loss of generality, LLR notation is used throughout the rest of this document. The sign of the LLR provides the bit estimation (i.e., positive LLR corresponds to v=0, and negative LLR corresponds to v=1). The magnitude of the LLR provides the reliability of the estimation (i.e., |LLR|=0 means that the estimation is completely unreliable; and |LLR|=∞ means that the estimation is completely reliable, and the bit value is known).
Usually, the messages passed during the decoding operation along the graph edges between bit nodes and check nodes are extrinsic. An extrinsic message m passed from a node n on edge e may take into account all the values received on edges connected to n other than edge e (this is why it is called extrinsic—it is based only on new information).
One example of a message passing decoding algorithm is the belief-propagation (BP) algorithm, which is one of the more common algorithms among this family of algorithms.
Let Pv denote the initial decoder estimation for bit v, based solely on the received or read symbol y, where Pv is a LLR value that may be defined as follows:
                              P          v                =                  log          ⁢                                          ⁢                                    Pr              ⁡                              (                                  v                  =                                      0                    |                    y                                                  )                                                    Pr              ⁡                              (                                  v                  =                                      1                    |                    y                                                  )                                                                        (        2        )            Note that it is also possible that some of the bits are not transmitted through the communication channel or stored in the memory device; hence there is no y observation for these bits. In this case, there are two possibilities:
First possibility: shortened bits. The bits are known a-priori and Pv=±∞, depending on whether the bit is 0 or 1.
Second possibility: punctured bits. The bits are unknown a-priori, where Pr(v=0) and Pr(v=1) are the a-priori probabilities that the bit v is 0 or 1, respectively. Assuming the information bits have equal a-priori probabilities to be 0 or 1, and assuming the code is linear, then:
                              P          v                =                              log            ⁢                                                  ⁢                                          1                /                2                                            1                /                2                                              =          0                                    (        3        )            
Let Qv denote the final decoder estimation for bit v, based on the entire received or read sequence y, and assuming that bit v is part of a codeword (i.e., assuming H·v=0), then:
                              Q          v                =                  log          ⁢                                          ⁢                                    Pr              ⁡                              (                                                      v                    =                                          0                      |                      y                                                        ,                                                            H                      ·                      v                                        =                    0                                                  )                                                    Pr              ⁡                              (                                                      v                    =                                          1                      |                      y                                                        ,                                                            H                      ·                      v                                        =                    0                                                  )                                                                        (        4        )            Let Qvc and Rcv denote a message from bit node v to check node c, and a message from check node c to bit node v, respectively, then a BP-algorithm utilizes the following update rules for computing the messages.
The bit node to check node computation rule is:
                              Q                                                            ⁢            vc                          =                              P            v                    +                                    ∑                                                c                  ′                                ∈                                                      N                    ⁡                                          (                                              v                        ,                        G                                            )                                                        ⁢                  \                  ⁢                  c                                                      ⁢                          R                                                c                  ′                                ⁢                v                                                                        (        5        )            Here N(n, G) denotes the set of neighbors of a node n in graph G and c′εN(v, G)\c refers to the neighbors excluding node c.
The check node to bit node computation rule is:
                                          R            cv                    =                                    φ                              -                1                                      (                                          ∑                                                      v                    ′                                    ∈                                                            N                      ⁡                                              (                                                  c                          ,                          G                                                )                                                              ⁢                    \                    ⁢                    v                                                              ⁢                              φ                ⁡                                  (                                      Q                                                                  v                        ′                                            ⁢                      c                                                        )                                                      )                          ,                              φ            ⁡                          (              x              )                                =                      {                                          sign                ⁡                                  (                  x                  )                                            ,                                                -                  log                                ⁢                                                                  ⁢                                  tanh                  ⁡                                      (                                                                                          x                                                                    2                                        )                                                                        }                                              (        6        )            Here, φ(x) and operations in the φ-domain are performed over the group {0, 1}×R+(this basically means that the summation here is defined as summation over the magnitudes and XOR over the signs). In a similar manner to equation (5), N(c, G) denotes the set of bit node neighbors of a check node c in graph G, and v′εN(c, G)\v refers to said neighbors excluding node v.
The final decoder estimation for bit ‘v’ is:
                              Q                                                            ⁢            v                          =                              P            v                    +                                    ∑                                                c                  ′                                ∈                                  N                  ⁡                                      (                                          v                      ,                      G                                        )                                                                        ⁢                          R                                                c                  ′                                ⁢                v                                                                        (        7        )            
A common feature of the soft decoding algorithm is that the decisions are dependent upon the history of the decoding iterations via equations (5), (6) and (7). The number of messages (for each iteration) in the soft decoding algorithm is proportional to the number of edges of the graph. This requires a large memory for storing the messages, or high computational complexity.
Hard decision decoding algorithms are usually much simpler than soft decision decoding algorithms, but do not perform as well. A typical class of hard decoding algorithms is the Bit Flipping (BF) algorithms. Under BF, the computations in each iteration are based on the current bit values are carried out, and some of the bit values are flipped according to the results of the computation. Only hard bit values are considered without assigning reliabilities to the bits.
For example, Majority Logic may be used for iteratively decoding certain LDPC codes. Under Majority Logic, decoding each iteration is associated with a specific bit. All the parity check equations in which the bit participates are computed. If the majority of the equations were not satisfied then the bit value of the specific bit is flipped. If the majority of the equations were satisfied then nothing is done in this iteration.
Many variants of both hard and soft decoding are found in the literature, and they all follow the general schemes presented above. Soft decoding algorithms include reliability measures together with bit values, the algorithms are more complex than the hard decoding algorithms and they perform better.